Sau thành công toàn cầu của album phòng thu thứ 8 Fever, Minogue bắt tay thực hiện album phòng thu thứ 9 Body Language.[3] Với mong muốn sáng tạo một album dance-pop lấy cảm hứng từ nhạc điện tử thập niên 1980,[4] Minogue tập hợp một nhóm cộng tác viên như Johnny Douglas (người từng hợp tác trong Light Years) và Karen Poole.[5] Cả hai cùng nhau sáng tác "Red Blooded Woman", trong khi Douglas đảm nhận vai trò sản xuất bài hát.[6] Bài hát phát hành làm đĩa đơn thứ hai trích từ Body Language trên toàn cầu vào ngày 1 tháng 3 năm 2004. Tại Anh Quốc, bài hát phát hành ngày 10 tháng 3 năm 2004.[5]

"Red Blooded Woman" là bài hát mang giai điệu hip hop và synthpop,[1][2] hai thể loại mới mà Minogue thể nghiệm trong album lần này.[3] Bài hát có chứa đoạn hook ghi hiệu ứng "Boy! Boy!" và "la la la ngọt lịm" lặp lại liên tục trong đoạn dẫn.[1][2] Theo Sal Cinquemani từ Slant Magazine, một đoạn nam hợp xướng cũng xuất hiện trong giọng nền theo lối "hồn ma".[2] Giống như nhiều bài hát trích từ album, "Red Blooded Woman" có ngụ ý đến dòng nhạc thập niên 1980: câu hát "You got me spinning round, round, round, round like a record" nhắc đến bài hát năm 1985 "You Spin Me Round (Like a Record)" của ban nhạc Vương quốc Anh Dead or Alive.[6][7] Các bản phối lại của những nghệ sĩ nhạc điện tử người Anh Narcotic Thrust và Whitey còn góp mặt trong phiên bản đĩa đơn ảnh 12-inch.[8]